package com.numberencoding;

import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class Trie {
    TrieNode root = new TrieNode(' ');

    void insertString(String s) {
        TrieNode v = root;
        for (char ch : s.toCharArray()) {
        	if (ch == '"') {
        		continue;
        	}
        	
            if (!v.children.containsKey(ch)) {
                v.children.put(ch, new TrieNode(ch));
            }
            v = v.children.get(ch);
        }
        v.isWord = true;
        v.word = s;
    }

	public boolean isPrefixExists(String prefix) {
		TrieNode v = root;
		
		for (char ch : prefix.toCharArray()) {
			if (!v.children.containsKey(ch)) {
				return false;
			} else {
				v = v.children.get(ch);
			}
		}
		return true;
	}
	
	public String getWord(String word) {
		TrieNode v = root;
		
		for (char ch : word.toCharArray()) {
			if (!v.children.containsKey(ch)) {
				return null;
			} else {
				v = v.children.get(ch);
			}
		}
		return v.word;
	}
	
	public String findAllWords(String digits, String input, List<String> result) {
		if (input.length() == 0) {
			return null;
		}
		
		TrieNode v = root;
		
		char [] chars = input.toCharArray();
		
		boolean found = false;
		
		for (int i=0; i < chars.length; i++) {
			char ch = chars[i];
			
			if (!v.children.containsKey(ch)) {
				if (found) {
					return findAllWords(digits, input.substring(i), result);
				} else {
					return null;
				}
			} else {
				v = v.children.get(ch);
			}
			
			if (v.isWord) {
				result.add(v.word);
				found = true;
			}
		}
		
		return v.isWord ? v.word : null;
	}
	
	private static class TrieNode {
        Map<Character, TrieNode> children = new TreeMap<Character, TrieNode>();
        boolean isWord;
        String word;
        char data;
		
        public TrieNode(char data) {
			this.data = data;
		}
    }
}